package com.zh.note.leetcode.sort;

import java.util.Arrays;

/**
 * 十大排序算法
 */
public final class SortUtil {

    /**
     * 冒泡排序
     * 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
     * 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
     * 3.针对所有的元素重复以上的步骤，除了最后一个；
     * 4.重复步骤 1~3，直到排序完成。
     */
    public static void bubbleSort(int arr[]) {

        for (int i = 0; i < arr.length; i++) {
            // 设置标志，true表示序列是有序的，没有发生交换
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    /**
     * 选择排序
     * <p>
     * 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
     * 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     * 3.重复第 2 步，直到所有元素均排序完毕。
     */
    public static void selectionSort(int arr[]) {

        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                swap(arr, i, min);
            }

        }


    }

    /**
     * 插入排序
     * 算法步骤
     * 1.从第一个元素开始，该元素可以认为已经被排序；
     * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
     * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 4.重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
     * 5.将新元素插入到该位置后；
     * 6.重复步骤 2~5。
     */
    public static void insertSort(int arr[]) {

        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                }
            }
        }

    }

    /**
     * 快速排序
     */
    public static void quickSort(int arr[], int low, int high) {
        if (low >= high) {
            return;
        }
        // 基准
        int temp = arr[low];
        int i = low;
        int j = high;
        while (i < j) {
            // 从右边开始找比基准数小的数(必须先从右边开始，不然排序不对)
            while (arr[j] >= temp && i < j) {
                j--;
            }
            //从左边开始找比基准数大的数
            while (arr[i] <= temp && i < j) {
                i++;
            }

            if (i < j) {
                swap(arr, i, j);
            }
        }

        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);

    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


    public static void main(String[] args) {
        int arr[] = {3, 1, 4, 2, 8, 7, 9, 5, 6};
        // bubbleSort(arr);
        // System.out.println(Arrays.toString(arr));
        // selectionSort(arr);
        // System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }


}
